package com.github.hgkmail.hello.leetcode101.binarysearch;

public class LC69SqrtX {
    public int mySqrt(int x) {
        //base case
        if (x==0) {
            return 0;
        }
        if (x==1) {
            return 1;
        }
        long l=1; //细节1：使用long，避免int溢出
        long r=x;
        long mid;
        while (l<=r) { //细节2：查找一个元素，要加等号，即l<=r
            mid=l+(r-l)/2; //细节3：这种写法能避免溢出，(r+l)/2 有可能导致int溢出的bug
            if (mid*mid==x) {
                return (int)mid;
            } else if (mid*mid>x) {
                r=mid-1;
            } else if (mid*mid<x) {
                l=mid+1;
            }
        }

        //细节4：平方根可能有小数，此时返回近似值 r
        return (int)r;
    }

    public static void main(String[] args) {
        System.out.println(new LC69SqrtX().mySqrt(8));
    }
}
